/*
https://leetcode-cn.com/problems/russian-doll-envelopes/solution/e-luo-si-tao-wa-xin-feng-wen-ti-by-leetc-wj68/
 */
import java.util.Arrays;

public class Solution354 {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a,b)->a[0]==b[0]?b[1]-a[1]:a[0]-b[0]);
        int[] f=new int[envelopes.length+1];
        int len=0;
        for (int i=0;i<envelopes.length;i++){
            if (envelopes[i][1]>f[len]){
                len++;
                f[len]=envelopes[i][1];
            }else{
                int l=1,r=len,t=-1;
                while (l<=r){
                    int mid=(l+r)/2;
                    if (f[mid-1]<envelopes[i][1] && envelopes[i][1]<=f[mid]){
                        t=mid;
                        break;
                    }else if (envelopes[i][1]>f[mid]){
                        l=mid+1;
                    }else{
                        r=mid-1;
                    }
                }
                f[t]=envelopes[i][1];
            }
        }
        return len;
    }

    public static void main(String[] args) {
        System.out.println(new Solution354().maxEnvelopes(new int[][]{{5,4},{6,4},{6,7},{2,3}}));
    }
}
